package algorithms.leaning.class19;

import common.util.MyUtil;

/**
 * 样本对应模型
 * <p>
 * str1 = "a123b45ct";
 * str2 = "1x2y345xf";
 * 返回就是 "12345"
 *
 * @author guichang
 * @date 2021/11/7
 */

@SuppressWarnings("all")
public class Code4_动态规划_最长公共子序列 {

    public static void main(String[] args) {
        String s1 = "a123b4r5ct";
        String s2 = "1x2y34q5xf";
        MyUtil.print(longestCommonSubsequence(s1, s2));
        MyUtil.print(longestCommonSubsequenceDp(s1, s2));
    }

    public static int longestCommonSubsequence(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return 0;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        return process(cs1, cs2, cs1.length - 1, cs2.length - 1);
    }

    /**
     * cs1的0~i和cs2的0~j的最长公共子序列长度
     */
    private static int process(char[] cs1, char[] cs2, int i, int j) {
        if (i == 0 && j == 0) {
            return cs1[i] == cs2[j] ? 1 : 0;
        }
        if (i == 0) {
            return cs1[i] == cs2[j] ? 1 : process(cs1, cs2, i, j - 1);
        }
        if (j == 0) {
            return cs1[i] == cs2[j] ? 1 : process(cs1, cs2, i - 1, j);
        }
        // i j都没到0的情况
        int p1 = process(cs1, cs2, i, j - 1);
        int p2 = process(cs1, cs2, i - 1, j);
        int p3 = cs1[i] == cs2[j] ? (1 + process(cs1, cs2, i - 1, j - 1)) : 0;
        return Math.max(p3, Math.max(p1, p2));
    }

    public static int longestCommonSubsequenceDp(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return 0;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int N = cs1.length;
        int[][] dp = new int[N][N];
        dp[0][0] = cs1[0] == cs2[0] ? 1 : 0;
        for (int j = 1; j < N; j++) {
            dp[0][j] = cs1[0] == cs2[j] ? 1 : dp[0][j - 1];
        }
        for (int i = 1; i < N; i++) {
            dp[i][0] = cs1[i] == cs2[0] ? 1 : dp[i - 1][0];
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                // i j都没到0的情况
                int p1 = dp[i][j - 1];
                int p2 = dp[i - 1][j];
                int p3 = cs1[i] == cs2[j] ? (1 + dp[i - 1][j - 1]) : 0;
                dp[i][j] = Math.max(p3, Math.max(p1, p2));
            }
        }
        return dp[N - 1][N - 1];
    }

}